/**
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

数据范围：字符串长度 0≤n≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
*/

import java.util.*;
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
       char[] arr= s.toCharArray();
        Stack<Character> stack=new Stack();
        for(int i=0;i<arr.length;i++){
          if(arr[i]=='('){
              stack.push(')');
          }else if(arr[i]=='['){
              stack.push(']');a
          } else if (arr[i]=='{'){
              stack.push('}');
          }else if(stack.isEmpty() || stack.pop()!=arr[i]){
              return false;
          }
          
        }
        return stack.isEmpty();
    }
}